Today's communications are to a great extent digital. They are both time discrete and discrete in amplitude, relying upon digital samples. Well-known examples of the technical development from analogue communications systems to digital communications systems are digitization for distribution of analogue telephony and the switch from vinyl records to audio compact discs, audio CDs in the 70's and 80's. Other examples have followed, such as portable digital audio players and digital television broadcasting.
For fixed analogue telephony, analogue speech is distributed in electrical signals over phone wires. When analogue telephone systems have been digitized, the speech is still carried in analogue electrical signals from the phone to a switch of the operator, where it is digitized so as to allow reconstruction within predefined requirements or criteria as regards distortion of the analogue signal. To provide required dynamics with a limited number of bits, the speech signal is compressed before the digitization providing a digital signal for distribution. The compressors provide signals of reduced dynamics but are essentially lossless, since the analogue signal could be expanded in a receiver. This compression is known as A-law or μ-law compression. At the receiving end, the signal is then expanded. Today there are also fixed telephone systems being digital all the way from one phone to another. In this description, compression is used for referring to lossy or lossless compression.
As regards CDs, analogue samples of time-continuous sound are quantized into a fixed number of bits (16 bits) with no compression of the quantized data. The limitation of sound samples to fixed levels provides some difference between the digitized samples and the analogue samples. This is known as quantization noise or distortion. Since the number of quantization levels is great (216), the distortion is negligible compared to the noise produced in analogue components of most audio CD players or amplifiers and loudspeakers.
As regards portable audio players and video broadcasting, the requirement on reducing the number of bits required for storage or transmission while not requiring too complex equipment requiring a huge amount of storage or power for feeding extremely fast (and power consuming) computers. Today, portable digital audio players and set top boxes for TV reception are available to many of those households that want them due to achievements of the technical development as regards, e.g., coding, storage media, such as flash memories, and computational capacity. Digital content stored on most portable digital audio players or broadcast in digital television or sound radio systems is compressed by lossy compression.
A communications channel may include media such as electromagnetic storage, electronic memories, propagation of signals in traveling waves of electromagnetic fields from a transmitting antenna to a receiving antenna, or propagation of optical signals from an optical transmitter to a receiver for optical signals.
Telephone systems, CDs, digital portable audio players and television broadcasting all provide examples of communications over a communications channel. The fixed wire provides a communications channel for the telephone system, the CD for the distribution of audio from a studio to a listener via a CD player, the flash memory or other storage medium for the portable audio player or the radio channel for television broadcasting.
R. M. Gray and D. L. Neuhoff, “Quantization,” IEEE Transactions on Information Theory, 1998, vol. 44, no. 6, pp. 2325-2383, traces the history of quantization from its origins, starting from 1898, and survey the fundamentals of many of the popular and promising techniques for quantization.
Gray and Neuhoff refer quantization to “the division of a quantity into a discrete number of small parts.” As an example, any real number can be rounded off to the nearest integer. In binary computing, integers are commonly represented by sequences of binary digits, bits, thereby providing a binary representation of the quantized real number. Other example data representations exist as well.
Quantization and source coding have their origins in pulse code modulation, PCM, the system used for audio CD recording. A PCM system consists fundamentally of three components: a sampler (11), a quantizer (12) and an encoder (13) as schematically illustrated in FIG. 1. Sampling converts a continuous time waveform (14) into a discrete time waveform (14). Quantization (12) of the samples (15) renders the quantized samples (16) to be approximations of the unquantized samples (15). The quantized samples, or indices thereof, are transmitted on a communications channel (17) as provided by the encoder (13). With scalar quantization, SQ, each (quantized) sample is independently encoded into a fixed number of bits, and correspondingly decoded into a reproduction. For a given distortion or reconstruction error, scalar quantization generally requires comparatively greater data rates than vector quantization, VQ.
Vector quantization, VQ, quantizes a number of samples simultaneously. VQ provides significantly higher quantization performance than scalar quantization, SQ, in the case of a fixed bit rate. In case of k successive samples to be quantized, VQ, makes use of a k-dimensional partition or a k-dimensional codebook, C, comprising k-dimensional code vectors, each code vector representing a cell of vectors with minimum distortion according to a predefined criterion, such as minimum Euclidean distance. For this purpose it is convenient to consider the quantization and encoding to be tightly related or one concept as schematically indicated by a dashed line (18) in FIG. 1. An advantage of VQ as compared to SQ is that it inherently can exploit memory of source signals to be quantized, source signals such as the discrete time sequence (14) of the sampled waveform. Thereby, source signals such as speech signals or image signals commonly comprising memory or dependencies between different samples can be represented more efficiently. Also VQ comprises merits on its own and, in principle, SQ cannot perform better in terms of distortion versus rate than the best VQ. In prior art, the price for this improvement has been paid by increased complexity of, particularly, the encoder.
FIG. 2 illustrates a simplified block diagram for vector quantization. A signal sequence (285) is represented by vectors (281) and signals (286) carrying the vectors are mapped (282) into an index (287) corresponding to a representation or codeword of the codebook, a code vector, providing a minimum distortion encoding of the vectors (286) according to a predefined criterion or measure, e.g. Euclidean distance. The vector to be represented (288) and the quantized vector or a representative thereof (289) are exchanged between the minimum distortion determining entity (282) and the entity comprising the code book representation (283). At the output of the channel (at a receiving end) the reconstructed vector is achieved by using a similar codebook and looking up the code vector represented by the received index.
Essentially, transmission on a communications channel comprises all technical arrangements for distributing or communicating a signal from a source sender to a destination as schematically illustrated in FIG. 3. A sequence representing a code index (34, 35) is transmitted through a communications channel (32) to the destination where it is decoded in the receiver (33). From the viewpoint of a source encoder and decoder, the channel may be considered to comprise channel coding as need be to transmit or detect errors on a transmission channel. In practice, though, channel encoders and decoders separated from the source encoding and decoding are included in physical transmitters and receivers, respectively. So, from the viewpoint of the source encoding, also parts of physical transmitters and receivers are frequently included in the communications channel (32).
For low bit rates, a good way to design a vector quantizer, from a rate distortion perspective, is to adapt the quantizer to characteristics of a given input source, e.g. provided in training sequences. FIG. 4 illustrates schematically a flowchart for iteratively determining a codebook Y according to a generalized Lloyd algorithm, frequently referred to as an LBG algorithm (as disclosed by Y. Linde A. Buzo and R. Gray). The algorithm is initiated (41) by initializing a counter m, an initial codebook Y0, a maximum possible (within the applicable range of the application) distortion D−1 and a precision level ε. For each iteration, m, a partitioning Sm defining the cells surrounding the various code vectors of the code book, is determined (42) for the code book Ym, and the distortion Dm is determined (43). The algorithm is interrupted (44) when the relative distortion is smaller than the precision set initially. In case the relative distortion is greater than the preset level, ε, a refined codebook is determined, the iteration counter is updated (46) and the process repeats for another iteration starting with determining a partitioning for the refined codebook (42).
The LBG algorithm is commonly considered to be computational expensive in terms of number of instructions when there is a great number of quantization levels. It is also sensitive to the initial choice of codebook (41). Also the amount of read-only memory, ROM, required by a trained vector quantizer is usually considered to be too large. Another problem is related to the LBG algorithm being trained to provide minimum distortion for a particular training data sequence. If data from another source with substantially different statistical properties is quantized, the performance is most often suboptimal. For vectors of dimension 1, the LBG quantizer reduces to the scalar Lloyd-Max quantizer.
For high bit rates, the theory of VQ provides a method for creating a codebook providing the smallest distortion, e.g. in terms of Euclidean distance or squared Euclidean distance, given a certain statistic of the input signal based on the calculation of a point density function from the probability density function, PDF, of the input signal. Structured codebooks do not exploit linear or non-linear dependency to increase the quantization performance that vector quantizers are generally capable of. At least linear dependencies, however, can be transformed to provide a benefit in quantization performance by means of Linear Prediction or Transform Coding. Therefore, the structured vector quantizers are designed such that they have high performance for memoryless sources.
A lattice vector quantizer is a vector quantizer of which the codebook is composed of vectors which are arranged in a regular lattice according to a mathematical rule. A degenerate example lattice quantizer is a uniform scalar quantizer for the special case of a vector quantizer of dimension Lv=1. Lattices in higher dimensions benefit from a more efficient space filling. In other words, a lattice, A, comprises all vectors in an Lv dimensional vector space with
                    L        ∷                  y          ∈                                    {                                                                                          ∑                                              j                        =                        0                                                                                              L                          L                                                -                        1                                                              ⁢                                                                  λ                        j                                            ·                                              v                        j                                                                              ∷                                                            λ                      j                                        ∈                    ℤ                                                  ,                                                                  ⁢                                                      v                    j                                    ∈                                      ℝ                                          L                      v                                                                                  }                        .                                              eq        .                                  ⁢        1            
where  denotes integers, and  denotes real Lv-tuples. The vectors v=[vi,0, vi,1, . . . , vi,LV−1] are the basis vectors of the lattice, and all lattice vectors are linear combinations of these basis vectors. The factors λj to weight each basis vector are integer numbers. A lattice in general is a subset of an Lv-dimensional vector space but consists of a countable infinite number of points,L⊂  eq. 2
The number, L, of weighting factors λi determines the lattice's degree of freedom and is also called the dimension of the lattice. L can be greater or smaller than Lv. In most cases, the dimension equals the dimension of the vector space in which the basis vectors are defined, LL=Lv.
For the case that the dimension of the lattice equals the dimension of the code-vector space, equation 1 is equivalent to a representation including a generator matrix M,L:yε{λ·M:λ=[λ0,λ1, . . . ,λLv−1],M=[v0T,v1T, . . . ,vLv−1T]},  eq. 3
where the factors λj as before are integer weight factors and Lv is the dimension of the vector space. When more than one matrix provide the same distribution of points considering all λ in equation 3, they are all generator matrices of one and the same lattice.
FIG. 5 illustrates an example two dimensional hexagonal lattice and corresponding basis vectors forming the generator matrix M. There are four vectors (51, 52, 53, 54) depicted. Vectors [1, 0] (51) and [½, √{square root over (3)}/2] (52) span the same set of points as do basis vectors [0, −√{square root over (3)}] (53) and [½, −√{square root over (3)}/2] (54).
An example generator matrix providing the lattice is consequently
                    M        =                              [                                                            1                                                                      1                    /                    2                                                                                                0                                                                                            3                                        /                    2                                                                        ]                    .                                    eq        .                                  ⁢        4            
Another example generator matrix of the lattice is
                              M          ′                =                              [                                                            0                                                  0                                                                                                                        -                                              3                                                              /                    2                                                                                        -                                          3                                                                                            ]                    .                                    eq        .                                  ⁢        5            
An alternative, but equivalent, definition of the two dimensional hexagonal lattice, also referred to as the A2 lattice, in FIG. 5 is
                              A          2                ∷                  y          ∈                                    {                                                                    [                                                                  y                        0                                            ,                                              y                        1                                            ,                      …                      ⁢                                                                                          ,                                              y                                                                              L                            v                                                    -                          1                                                                                      ]                                    ∷                                      y                    ∈                                          ℝ                                              L                        v                                                                                            ,                                                                  ⁢                                                                            ∑                                              j                        =                        0                                                                                              L                          v                                                -                        1                                                              ⁢                                          y                      j                                                        =                  0                                            }                        .                                              eq        .                                  ⁢        6            
Jacques Martinet, “Perfect Lattices in Euclidean Spaces,” Springer-Verlag, Berlin, 2003, pp. 110-114, defines lattices of prior art such as the hexagonal lattice, ALv, and its dual, A*Lv, the checkerboard lattice, DLV, and its dual D*Lv, and the integer lattice, ZLv, for arbitrary dimensions Lv. In the sequel, the printing symbol asterisk will be used for other purposes than for denoting a dual lattice.
Other known lattices are the Gosset lattice, E8, the Coxeter-Todd-Lattice, K12, the Barnes-Wall lattice L16, and the Leech Lattice L24.
A permutation code P defines all vectors of a codebook by means of class-leader vectors, {tilde over (x)}P, of dimension Lv. A class-leader vector {tilde over (x)}P is composed of coordinate entries {tilde over (x)}P,j, 0≦j<Lv, comprising wj components taken from a set of LP≦Lv real values, μl, 0≦l<LP, sorted in decreasing order, μ0>μ1> . . . >μLP−1,
                                                                                          x                  ~                                P                            =                                                [                                                                                                              x                                                      P                            ,                            0                                                                                                                                                x                                                      P                            ,                            1                                                                                                                      …                                                                                              x                                                      P                            ,                                                                                          L                                v                                                            -                              1                                                                                                                                                            ]                                T                                                                                        =                                                                    [                                                                                                                                                      μ                              0                                                        ⁢                                                                                                                  ⁢                                                          μ                              0                                                        ⁢                                                                                                                  ⁢                            …                            ⁢                                                                                                                  ⁢                                                          μ                              0                                                                                                                                                                                          μ                              1                                                        ⁢                                                                                                                  ⁢                                                          μ                              1                                                        ⁢                                                                                                                  ⁢                            …                            ⁢                                                                                                                  ⁢                                                          μ                              1                                                                                                                                …                                                                                                                                    μ                                                                                                L                                  P                                                                -                                1                                                                                      ⁢                                                                                                                  ⁢                                                          μ                                                                                                L                                  P                                                                -                                1                                                                                      ⁢                                                                                                                  ⁢                            …                            ⁢                                                                                                                  ⁢                                                          μ                                                                                                L                                  P                                                                -                                1                                                                                                                                                                                                                                      ←                                                                                          w                                0                                                            →                                                                                                                                                            ←                                                                                          w                                1                                                            →                                                                                                                                …                                                                                                      ←                                                                                          w                                                                                                      L                                    P                                                                    -                                  1                                                                                            →                                                                                                                                            ]                                    T                                .                                                                        eq        .                                  ⁢        7            
wl is the weight related to real value μl and is the number of occurrences of real value μl, 0≦l<LP,
                                          ∑                          l              =              0                                                      L                P                            -              1                                ⁢                      w            l                          =                              L            v                    .                                    eq        .                                  ⁢        8            
A permutation of a class-leader vector {tilde over (x)}P is a vector {tilde over (x)}*P that is composed of the same real values, μl, as {tilde over (x)}P but in a different order. The corresponding permutation operation can be specified by means of matrix, P, referred to as the permutation matrix. The relation between {tilde over (x)}P and {tilde over (x)}*P could then be expressed as{tilde over (x)}*P=P·{tilde over (x)}P=[{tilde over (x)}*P,0{tilde over (x)}*P,1 . . . {tilde over (x)}*P,Lv−1]T.  eq. 9
An example permutation vector reversing the sequence order is
                    P        =                              [                                                            0                                                  …                                                  0                                                  0                                                  1                                                                              0                                                  …                                                  0                                                  1                                                  0                                                                              …                                                  …                                                  …                                                  …                                                  …                                                                              0                                                  1                                                  0                                                  …                                                  0                                                                              1                                                  0                                                  0                                                  …                                                  0                                                      ]                    .                                    eq        .                                  ⁢        10            
The permutation processing is preferably realized in a digital signal processor, DSP, adapted for the permutation of interest. High speed applications may require the permutations to be implemented in hardware, which can be achieved by employment of e.g. shift register circuitry. Reversal of sequence order is e.g. achieved by storing the vector components in a shift register of the same length as the vector, in component-wise sequential order, and feeding out the shift register content in the reverse order. This is illustrated in FIG. 6. The example shift register is composed of a number of D latches (601-603). The vector to be reversed is input (604) to the shift register through closed switches (605-607) during a sequence of clock cycles during which one component of the vector is input after another. When the entire vector has been shifted into the D elements (601-603), the previously closed switches (605-607) are being opened, and switches (608-610), previously open while shifting the vector into the register, are being closed. During the next clock cycles, the components are shifted out of the shift register (611) in reverse order. Effectively, the shift register of FIG. 6 could be replaced by memory circuitry or a storage medium for storing controlled by a signal processor. The corresponding processing comprises storing the vector components in the memory or storage medium and reading out the memory content or stored content component wise in the reverse order.
Given a class-leader vector and corresponding weights wl, the number of possible permutations is
                                          N            P                    =                                                                      (                                                            ∑                      l                                        ⁢                                          w                      l                                                        )                                !                                                              ∏                  l                                ⁢                                                      w                    l                                    !                                                      .                          ,                            eq        .                                  ⁢        11            
NP is known as the multinomial coefficient. To identify one among all possible permutations, a vector index iP, 0≦iP<NP, is useful for describing and understanding the encoding process and mapping of code vectors. Since all permuted vectors are composed of the same coordinate values but in different order, the absolute value, or length, of the code vectors is identical for all permutated vectors. Using the vector index, this is∥{tilde over (x)}iP∥=√{square root over (Σlwl·μl2)}∀iP.  eq. 12
The NP permutations of the class-leader vector altogether form a permutation codebook {tilde over (X)}P.
A further issue in the quantization process relates to compaction or how to represent the various vectors with fewer class representatives, such that the errors introduced by information loss due to the compaction will be acceptably small, or at best not be noticeable, to a user.
One representation of a vector x based on the class-leader vector, {tilde over (x)}P of a permutation code that provides the minimum Euclidean distance is achieved as follows. For a vector x of dimension Lv, x=[x0 x1 . . . xLv−1]T to be (further) quantized or compacted, permute the vector coordinates such that the components of the permuted vector x*=[x*0 x*1 . . . x*Lv−1]T are ordered in decreasing order x*0≧x*1≧ . . . x*Lv−1. The required permutations are represented by a matrix Px, x*=Px·x. The ordered vector x* is represented by a class-leader vector as specified in equation 7 and that also has its components sequentially ordered according to magnitude.
For reconstructing x from x*, the process is reversed x=(Px)−1·x*. The matrix P=(Px)−1 also provides a minimum Euclidean distance representative {tilde over (x)}*P for the vector x to be quantized or compressed.{tilde over (x)}*P=(Px)−1·{tilde over (x)}P.  eq. 13
To achieve the compression a vector index, iP, is determined for the vector representative {tilde over (x)}*P. This is achieved by a permutation to index mapping and which is preferably achieved by a mapping suggested by J. Pieter and M. Schalkwijk.
The mapping consequently transforms the permuted vector {tilde over (x)}*P into an index iP. A decoder realizes the reverse operation and maps the index iP back into a permuted vector {tilde over (x)}*P, corresponding to the original permuted vector. Consequently, there is a one-one mapping between permuted vector {tilde over (x)}*P and index iP, the index iP providing a representation of the permuted vector {tilde over (x)}*P suitable for transmission, storage or further processing such as for channel encoding. In brief, the index is suitable for transfer on a communications channel. The number of indices, |IP|, is equal to the number of possible permutations, NP (see equation 11).
U.S. Pat. No. 4,075,622 describes a method and apparatus for data compression which utilizes a random walk through Pascal's triangle directed by an incoming binary source sequence. The random walk starts at the apex of Pascal's triangle and proceeds downward according to an algorithm until it terminates at a boundary which has been constructed in such a way that the encoding of each source sequence can be accomplished in a fixed number of bits.
U.S. Pat. No. 6,054,943 describes a variable-to-block universal multilevel digital information compression making use of a random walk in Pascal's hypervolume, a multi-dimensional generalization of Pascal's triangle. Codewords and decoded source sequences are either determined in the encoder and decoder, respectively, on the fly at encoding/decoding or pre-computed and stored. Variable length sequences of source symbols are encoded into fixed length codeword blocks. Encoders and decoders including dedicated hardware including registers, counters and latches are disclosed as are flowcharts. FIG. 26 of U.S. Pat. No. 6,054,943 illustrates graphically an example encoding (and decoding) of an example sequence of a ternary source. Depending on the source sequence and for each incoming source symbol, a particular candidate prefix is selected and a running sum is updated. The final value of the running sum, rs, for a sequence of symbols {jk}k=1n corresponds at least to a part of an index or codeword and equals
                              rs          =                                    ∑                              k                =                1                            n                        ⁢                                          ∑                                  i                  =                  0                                                                      j                    k                                    -                  1                                            ⁢                                                                    (                                          k                      -                      1                                        )                                    !                                                                                            (                                                                        w                          i                          k                                                -                        1                                            )                                        !                                    ⁢                                                            ∏                                                                        p                          =                          0                                                                          p                          ≠                          i                                                                                            m                        -                        1                                                              ⁢                                                                  (                                                  w                          p                          k                                                )                                            !                                                                                                          ,                            eq        .                                  ⁢        14            
where jkε[0, m−1] is the incoming symbol at stage k and where the summation is over all n incoming symbols and wik is the number of symbols iε[0, m−1] that have arrived after k stages. The outer sum is determined recursively by adding the inner summation for each incoming symbol to encode. The encoding is terminated at a particular element in Pascal's hyper volume. This point is added as a starting point prefix for the decoder to know where to start tracing back in Pascal's hyper volume. It is also suggested in U.S. Pat. No. 6,054,943 to add a prefix to allow uncoded transmission in order to avoid encoder expansion to happen for some sequences. At encoding, a recursion for determining the running sum for an incoming symbol j is
                              rs          ←                      rs            +                                          ∑                                  i                  =                  0                                                  j                  -                  1                                            ⁢                              oldPos                *                                                      w                    i                                                                              w                      j                                        +                    1                                                                                      ,                            eq        .                                  ⁢        15            
where oldPos is the old position in Pascal's hyper volume. The position in Pascal's hyper volume is similarly updated recursively for the next iteration,
                              l          ←                      l            +            1                          ,                            eq        .                                  ⁢        16                                          oldPos          ←                      oldPos            *                          l                                                w                  j                                +                1                                                    ,                            eq        .                                  ⁢        17            
where l corresponds to the number of symbols that have come in.
The recursion for decoding works the path through Pascal's hyper volume for choosing a symbol j that provides a position that is not greater than a candidate for the corresponding position in the hyper volume. The recursion for the running sum in reverse direction, decoding position l of a codeword, in U.S. Pat. No. 6,054,943 is
                              rs          ←                      rs            -                                          ∑                                  i                  =                  0                                                  j                  -                  1                                            ⁢                              curPos                *                                                      w                    i                                    l                                                                    ,                            eq        .                                  ⁢        18            
with the associated recursions decoding next
                    l        ←                  l          +          1                                    eq        .                                  ⁢        19                                curPos        ←                  curPos          *                                                    w                j                            l                        .                                              eq        .                                  ⁢        20            
Khalid Sayood, “Introduction to Data Compression, 2nd edition, 2000, pp. 290, 291” provides a first introduction to spherical vector quantizers. For the Gaussian probability distribution, the contours of constant probability are circles in two dimensions. In two dimensions an input vector can be quantized by transforming it into polar coordinates comprising radius, r, and phase, θ. Polar coordinates span the same space as do Cartesian coordinates. r and θ can either be quantized independently, or quantized values of r can be used as an index to a quantizer for θ. The advantage to quantizing r and θ independently is reduced complexity as compared to a quantizer for which the quantization of θ depends on the quantization of r. As mentioned above in relation to scalar quantizers, not making full use of interdependencies within a block tend to reduce performance.
Jon Hamkins, ‘Design and analysis of spherical codes,’ Thesis submitted in partial fulfillment of the requirements for the degree of Doctor of philosophy in Electrical Engineering in the Graduate College of the University of Illinois at Urbana-Champaign, dated 1996, briefly defines and provides properties of the root lattices Ak, Dk, E8 and Zk and their duals in chapter 2, the “root” relating to the root systems of certain Lie algebras. Hamkins also defines a codebook as a set of output points or vectors forming the code points or code vectors. A k-dimensional spherical code is defined as a finite set of points in  that lie on the surface of the k-dimensional unit radius sphere Ωk,
                              Ω          k                ≡                              {                                                            (                                                            x                      1                                        ,                                          x                      2                                        ,                    …                    ⁢                                                                                  ,                                          x                      k                                                        )                                ∈                                                      ℝ                    k                                    :                                                            ∑                                              i                        =                        1                                            k                                        ⁢                                          x                      2                                                                                  =              1                        }                    .                                    eq        .                                  ⁢        21            
In chapter 6, Hamkins describes wrapped spherical codes as vector quantizers for a memoryless Gaussian source and provides an algorithmic description of an encoder in table 6.1 quantizing gain and shape of a vector independently, the gain corresponding to the length or radius of the vector, and the shape corresponding to the vector normalized to 1. The gain codebook is optimized by the Lloyd-Max algorithm. Since the PDF is known (Gaussian source), no training is required. The algorithmic description is also included in Jon Hamkins and Kenneth Zeger, Gaussian Source Coding with Spherical Codes, IEEE Transactions on Information Theory, vol. 48, No. 11, pp. 2980-2989 (2002).